// -*- C++ -*-
//
//  This file is part of Siena, a wide-area event notification system.
//  See http://www.inf.usi.ch/carzaniga/siena/
//
//  Authors: Antonio Carzaniga
//  See the file AUTHORS for full details. 
//
//  Copyright (C) 2003-2004 University of Colorado
//  Copyright (C) 2005 Antonio Carzaniga
//
//  This program is free software; you can redistribute it and/or
//  modify it under the terms of the GNU General Public License
//  as published by the Free Software Foundation; either version 2
//  of the License, or (at your option) any later version.
//
//  This program is distributed in the hope that it will be useful,
//  but WITHOUT ANY WARRANTY; without even the implied warranty of
//  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//  GNU General Public License for more details.
//
//  You should have received a copy of the GNU General Public License
//  along with this program; if not, write to the Free Software
//  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307,
//  USA, or send email to one of the authors.
//
//
// $Id: b_predicate.h,v 1.4 2010-03-11 15:16:37 carzanig Exp $
//
#ifndef B_PREDICATE_H
#define B_PREDICATE_H

#ifdef HAVE_CONFIG
#include "config.h"
#endif

#include "siena/types.h"
#include "siena/forwarding.h"
#include "siena/allocator.h"

#include "bset.h"
#include "bset_encoding.h"

namespace siena {
    /** @brief a filter in a BTable.
     *
     *  a filter is simply a link in a linked list that contains a
     *  Bloom filter, which represents the conjunction of constraints.
     **/
    struct BFilter {
	BFilter * next;
	bset_t b;
    
	BFilter(BFilter * n, const bset_t & x) : next(n), b(x) {};
    };

    template<class BFilterT>
    BFilterT * encode_predicate(const predicate & p, FTAllocator & mem) 
	throw(bad_constraint) {
	BFilterT * flist = 0; 
	predicate::iterator * pi = p.first();
	if (pi) {
	    do {
		bset_t b;
		encode_filter(b, pi);

		bool must_add = true;
		for(BFilterT * f = flist; f != 0; f = f->next) {
		    if (b.covers(f->b)) {
			//
			// NOTICE: this "covers" relation is defined
			// in the sense of the Bloom filter coverage,
			// i.e., b1 covers b2 if all the 1-bit
			// positions of b2 are also 1-bit positions of
			// b1.  In other words, if ((b1 & b2) == b2).
			// Because of the semantics of the Bloom
			// filter encoding, this relation is exactly
			// the opposite of the usual covering
			// relations.  This is why, we do not add new
			// filters that cover previous filters (in the
			// sense of the Bloom filter), and instead we
			// swap in the new filter whenever that *is
			// covered* by a previous filter.
			//
			must_add = false;
			break;
		    } else if (f->b.covers(b)) {
			f->b = b;
			//
			// not only we replace the old one with the
			// new one here, but we must also remove all
			// other previous filters that are also
			// covered (in the sense of the Bloom filter)
			// by the new one.  So, this is what we do
			// with this loop.
			//
			while (f->next) {
			    if (f->next->b.covers(b)) {
				f->next = f->next->next;
			    } else {
				f = f->next;
			    }
			}
			must_add = false;
			break;
		    }
		}
		if (must_add) {
		    flist = new (mem)BFilterT(flist, b);
		}
	    } while(pi->next());
	    delete(pi);
	}
	return flist;
    }
} // end namespace siena

#endif
